This application is based upon and claims the benefit of priority from the prior Japanese Patent Application No. 2001-011760, filed Jan. 19, 2001, the entire contents of which are incorporated herein by reference.
1. Field of the Invention
The present invention relates to an associative memory and more particularly to a small-area, associative memory with fast parallel minimum-distance-search capability, used for artificial intelligence systems, data-bank systems, mobile network terminals and the like.
2. Description of the Related Art
Conventionally, an associative memory is activated by searching for the xe2x80x9cbest match dataxe2x80x9d between an input data composed of W units, each k bits long, and R reference data, each also composed of W units, each k bits long. The associative memory has a function of generating comparative bits to clarify the best match data by comparing stored reference data with input data, also called search data or match data, input from outside.
The xe2x80x9cbest match dataxe2x80x9d is defined as data with the smallest measure, which is of distance here. As the measure of distance, conventionally, the Hamming distance and Manhattan distance are best known. The Hamming distance is used for data strings, voice patterns, black-and-white pictures and the like, and the Manhattan distance is used for color pictures, gray-scale pictures and the like.
If the bit length of a unit of input data or reference data is 1 bit (k=1), the Hamming distance is applied. That is, the Hamming distance is defined as the number of bits that are different from each other in two items of data to be compared.
On the other hand, if the input data is composed of units of coded numbers such as Xin={x1, x2, x3, . . . xW}, Yref={y1, y2, y3, . . . yW}, the Manhattan distance is applied. At this time, the Manhattan distance between two items of data is defined as follows.                                           D                          M              ⁢                              xe2x80x83                            ⁢              a              ⁢                              xe2x80x83                            ⁢              n              ⁢                              xe2x80x83                            ⁢              h                                ≡                      ∑                          i              =              1                        W                          |                              x            i                    -                      y            i                          |                            (        1        )            
Basically, the following methods have been used to search for the best matching of most similar data (hereinafter referred to as the winner) according to conventional art. That is,
(a) Use of an analog neural network (H. P. Graf and L. D. Jackel, xe2x80x9cAnalog Electronic Neural Network Circuitsxe2x80x9d, IEEE Circuits and Device Mag., vol. 5, p. 44, 1989),
(b) Use of plural SRAMs and separate digital search circuits (A. Nakada et al., xe2x80x9cA Fully Parallel Vector-Quantization Processor for Real-Time Motion Picture Compressionxe2x80x9d, IEEE Journ. Solid-State Circuits, vol. 34, pp. 822-830, 1999; T. Nozawa et al., xe2x80x9cA Parallel Vector Quantization Processor Eliminating Redundant Calculations for Real-time Motion Picture Compressionxe2x80x9d, ISSCC Digest of Tech. Papers, pp. 234-235, 2000),
(C) Use of an analog winner-take-all circuit (Analog Winner-Take-All circuit; WTA circuit) employing MOS transistors used as source-followers (S. M. S. Jalalenddine and L. G. Johnson, xe2x80x9cAssociative IC Memories with Relational Search and Nearest-Match Capabilitiesxe2x80x9d, IEEE Journ. Solid-State Circuits, vol. 27, pp. 892-900, 1992).
However, these methods have the following problems. That is, because the circuit complexity of the search circuit increases in order of R2 (O(R2)) or in order of R*W (O(R*W)), the occupied area in a chip increases (see the documents in (a) and (b), above) and furthermore the time necessary for searching is increased (about 1 xcexcs). Another problem is that the searchable range only extends to a small W (see the document in (c), above).
Conventionally, in an artificial intelligence system using associative memory, hardware having a high area efficiency is almost impossible to achieve; therefore, generally, artificial intelligence systems are constructed on high-performance computers using complicated software.
There have not yet been any mobile terminals capable of video communication. The reason is that if video data-compression technologies such as MPEG are employed, a tremendous amount of hardware is needed in the sender/receiver terminal. With an associative memory, a data compression method based on a code book can be used (A. Nakada et al., xe2x80x9cA Fully Parallel Vector-Quantization Processor for Real-Time Motion Picture Compressionxe2x80x9d, IEEE Journ. Solid-State Circuits, vol. 34, pp. 822-830, 1999).
According to this method, first, a data stream is divided into blocks of a specified number of bits and next, best match blocks, which are those most similar to the ones in the code book, are determined using the associative memory. In the final stage, only the identifier of a block is transmitted to the receiver. The data transmitted in this way is reconstructed according to the code book. Therefore, the receiver can be constructed with a very simple structure.
This technology is suitable for transmission of video signals and is called vector quantization. The associative memory of the present invention is advantageously used in fields of bandwidth compression of video signal in mobile communication terminals, artificial intelligence systems, data bank systems and the like with plural compact chips or a single compact chip.
As described above, the problem with the conventional winner search method is that if the unit number W of input data or the number R of reference data increases, the circuit complexity of the search circuit strongly increases proportionally to R2 so that the required chip area strongly increase and searching takes longer.
The present invention has been developed to solve the above problems and, therefore, an object of the present invention is to provide an associative memory capable of fast parallel searching with a search circuit implemented on a small chip area by avoiding an increase in the number of circuits proportionally to R2 and reducing this increase to be proportional to R. Such an associative memory is intended to be applied to the fields of bandwidth compression of video signals in mobile communication, including mobile network terminals, artificial intelligence and the like.
To achieve the above-described objective according to the present invention, there is an associative memory with a fast parallel minimum-distance-search capability, which is formed of a CMOS circuit, realizing fast search with a small chip area by avoiding a strong increase in the number of circuits even if the unit number W of the input data or the number R of the reference data is large.
Specifically, the present invention provides a semiconductor associative memory including a memory array comprising: unit storage circuits each having k bits arranged in R rows of W columns (R, W, k are natural numbers); unit comparison circuits arranged in R rows of W columns for comparing input data of Wxc3x97k bits with reference data of W k-bit units stored in the unit storage circuits at every k bit; weighted word comparators for weighting each bit of output data output from each row of the unit comparison circuit; row decoders of R rows; and column decoders of Wxc3x97k columns.
Preferably, the unit in the memory array is composed of binary-coded data and the bit number k of the unit is k=1 in the case where the Hamming distance is used to search for reference data matching with the input data and k greater than 1 in the case where the Manhattan distance is used.
Further, preferably, in the case where the retrieval of the reference data based on the input data is carried out using the Hamming distance, the unit storage circuit is composed of an SRAM memory cell, the unit comparison circuit comprises a 2-input EXOR circuit or a 2-input EXNOR circuit each connected to the complementary output portion of a latch circuit constituting the SRAM memory cell, the weighted word comparator including a transistor, or two transistors connected to each other in series connected to the 2-input EXOR circuit or EXNOR circuit.
Further, preferably, in the case where retrieval of the reference data based on the input data is carried out using the Manhattan distance, the unit storage circuit includes a complementary input section and a complementary output section of k ( greater than 1) bits, the unit comparison circuit includes a function for subtracting the output signal of the complementary output section from the input signal of the complementary input section and a function for calculating the absolute value of the result of the substraction, the weighted word comparator comprises transistors or groups of two transistors connected to each other in series connected to each of the k bits of the output portion of the unit comparison circuit.
Further, preferably, weighting of the output data in the weighted word comparator is carried out by selecting the value of the ratio of the gate width to the gate length of any one of the one transistor or the two transistors connected to each other in series, constituting the weighted word comparator.
Further, preferably, the semiconductor associative memory comprises a winner line-up amplifier providing connections to each row of the memory array, the winner line-up amplifier consisting of a winner/loser distance amplification unit, a feedback signal generation section included in the winner/loser distance amplification unit, a comparison signal regulation unit for regulating the comparison signal of the weighted word comparator of each of the W rows so that the amplification factor of the winner/loser distance amplification unit is maximized using a feedback signal output from the feedback signal generation section, and a feedback signal coding section for outputting the match quality of the winner by coding the feedback signal.
Further, preferably, the winner/loser distance amplification unit comprises a push-pull amplifier, two transistors for receiving an inverted and not-inverted enable signals and a compensation capacitor provided on each row of the memory array, as well as the feedback signal generation section consisting of a source-follower pull-down transistor provided on each row of the memory array for receiving the output of the push-pull amplifier to the gate, and pull-up transistors common to all rows of the memory array and connected to each of the pull-down transistors in series. Further, preferably, the comparison signal regulation unit comprises a pass transistor for regulating the output signal current from the weighted word comparator, and a source-follower pull-up transistor for converting the output signal current to an intermediate potential, wherein the feedback signal is input to the gate of the source-follower pull-up transistor while the enable signal is input to the gate of the pass transistor.
Further, preferably, the winner/loser distance amplification unit comprises a current mirror amplifier and a compensation capacitor provided on each row of the memory array, as well as the feedback signal generation section including a Min/Max circuit which operates at high speeds. Further, preferably, the comparison signal regulation unit includes a source-follower pull-up transistor for converting the output signal current from the weighted word comparator to an intermediate potential, and a level shifter for shifting the feedback signal in terms of its voltage level and inputting the signal into the source of each transistor constituting the weighted word comparator.
Further, preferably, the semiconductor associative memory comprises a winner-take-all circuit providing connections to each output of the winner-line-up amplifier, the winner-take-all circuit including a level shifter configured as required, winner-take-all amplifiers of n stages (n is a positive integer) in order to amplify the output signal of the winner/loser distance amplification unit further, and a final decision circuit connected to the output portion of the n-th stage of the winner-take-all amplifier.
Further, preferably, a winner-take-all amplifiers includes a level shifter and a winner-take-all amplifier of a single stage; the level shifter regulating the level of the output signal voltages of the winner/loser distance amplification unit so that the amplification factor of the winner-take-all amplifier of the single stage is maximized; the winner-take-all amplifier of the single stage including transistors for converting the level shifter output signal voltages to current changes in the amplifier and transistors for converting the current changes in the amplifier to output signal voltages of the winner-take-all amplifier of the single stage; the winner-take-all amplifier of the single stage including a final decision circuit, provided at the output portion thereof, composed of inverters with adjusted switching-threshold voltages so as to match the output signal voltages of the winner-take-all amplifier.
Further, preferably, the winner-take-all circuit includes a level shifter and winner-take-all amplifiers of n stages (n is an integer greater than 1); the level shifter regulating the level of the output signal voltages of the winner/loser distance amplification unit so that the amplification factor of the winner-take-all amplifier of the first stage is maximized; the winner-take-all amplifier of the first stage including transistors for converting the level shifter output signal voltages to current changes in the amplifier and transistors for converting the current changes in the amplifier to output signal voltages of the winner-take-all amplifier of the first stage; the winner-take-all amplifier of the i-th stage (i is an integer greater than 1 but less than n) including transistors for converting the output signal voltages of the (ixe2x88x921)-th stage to current changes in the amplifier of the i-th stage and transistors for converting the current changes in the amplifier of the i-th stage to output signal voltages of the winner-take-all amplifier of the i-th stage; the winner-take-all amplifier of the n-th stage including a final decision circuit, provided at the output portion thereof, composed of inverters with adjusted switching-threshold voltages so as to match the output signal voltages of the winner-take-all amplifier of the n-th stage.
Further, preferably, the feedback signal is input to the source of each transistor constituting the weighted word comparator or the gate of any one of the two transistors connected to each other in series constituting the weighted word comparator.
Further, preferably, when the conductivity type of each transistor constituting the weighted word comparator is inverted, the conductivity type of each transistor constituting the winner/loser distance amplification unit and the feedback signal generation section is inverted, the polarity of the enable signals of the winner/loser distance amplification unit and the feedback signal generation section are reversed and the conductivity type of the transistors constituting the winner-take-all circuit is inverted, while the power supply terminals and grounding terminals of the winner/loser distance amplification unit, the feedback signal generation section and the winner-take-all circuit are exchanged.
Further preferably, the number of transistors constituting the winner line-up amplifier and the winner-take-all circuit is proportional to the number of rows R in the memory field.